#!/usr/bin/python
# -*- coding: utf-8 -*-
'''
基本思想：
1）选择一个基准元素,通常选择第一个元素或者最后一个元素,
2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
3）此时基准元素在其排好序后的正确位置
4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

不稳定
'''

def QuickSort(a):
     if len(a) <= 1:
         return a  # 如果a為一位數則直接傳回a

     def smaller(x):
         if x < a[0]:
             return x

     def bigger(x):
         if x > a[0]:
             return x

     l=filter(smaller,a[1:])# 輸出排序後的比a[0]小的數列
     r=filter(bigger,a[1:])# 輸出排序後的比a[0]大的數
     #l = [x for x in a[1:] if x <= a[0]]  # 輸出排序後的比a[0]小的數列
     #r = [x for x in a[1:] if x > a[0]]  # 輸出排序後的比a[0]大的數
     return QuickSort(l) + [a[0]] + QuickSort(r)


if __name__ == '__main__':
    lists = [49, 38, 65, 97, 76, 13, 27, 49]

    print QuickSort(lists)